package com.zlp.partice;

import org.junit.Test;

import java.util.*;

/**
 * @Author: zhulaiping
 * @Date: 2021/8/27 9:56
 */
class MedianFinder {

    int cnt;
    int[] map;
    /** initialize your data structure here. */
    public MedianFinder() {
        map = new int[101];
    }
    public void addNum(int num) {
        cnt++;
        map[num]++;
    }

    public double findMedian() {
        int cur;
        if((cnt&1)==0){
            cur = cnt/2;
            for (int i=0;i<101;i++){
                if(map[i]==0)continue;
                cur-=map[i];
                if(cur<0) return i;
                if(cur==0){
                    int l = i;
                    while (map[++i]==0);
                    return (l+i)*1.0/2;
                }
            }
        }else {
            cur = cnt/2+1;
            for (int i=0;i<101;i++){
                if(map[i]==0)continue;
                cur-=map[i];
                if(cur<=0) return i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        double a = medianFinder.findMedian();
        medianFinder.addNum(3);
        double b = medianFinder.findMedian();
    }

    public int[] runningSum(int[] nums) {
        for (int i=1;i<nums.length;i++){
            nums[i] += nums[i+1];
        }
        return nums;
    }
    public int sumOddLengthSubarrays(int[] arr) {
        int ret = 0,len = arr.length;
        for (int i=0;i<len;i++){
            int cnt = 0;
            for (int j=i;j<arr.length;j++){
                cnt++;
                if(cnt%2==1) ret += arr[j];
            }
        }
        return ret;
    }

    static class Solution{
        Random random = new Random();
        int[] map;
        public Solution(int[] w) {
            map = new int[w.length+1];
            for (int i=1;i<=w.length;i++){
                map[i] = w[i-1]+map[i-1];
            }
        }
        public int pickIndex() {
            if(map.length==2) return 0;
            int value = random.nextInt(map[map.length-1]);
            //如果value在[w[i-1]-w[i])就返回i;
            int l = 1,r = map.length-1;
            while (l<r){
                int mid = l + (r-l>>1);
                if(value>=map[mid]){
                    l = mid+1;
                }else if(value<map[mid-1]){
                    r = mid-1;
                }else return mid-1;
            }
            return l-1;
        }

        public static void main(String[] args) {

           Solution s = new Solution(new int[]{1,3,4,5});
           /* int i = s.pickIndex();
            int i1 = s.pickIndex();
            int i2 = s.pickIndex();
            System.out.println(i);
            System.out.println(i1);
            System.out.println(i2);*/
            for (int i=0;i<30;i++)
                System.out.print(s.random.nextInt(13)+"  ");
        }

        public int[] corpFlightBookings(int[][] bookings, int n) {
            int[] ret = new int[n];
            for (int[] cur:bookings){
                int x = cur[0]-1,y = cur[1],val = cur[2];
                ret[x] += val;
                if(y<n) ret[y] -= val;
            }
            for (int i=1;i<n;i++){
                ret[i] += ret[i-1];
            }
            return ret;
        }
    }

    int[] ret;
    int[] cache;
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        List<Integer>[] map = new List[quiet.length];
        int[] pos = new int[quiet.length];
        for (int[] arr:richer){
            if(map[arr[1]] == null){
                map[arr[1]] = new ArrayList<>();
            }
            map[arr[1]].add(arr[0]);
        }
        for (int i=0;i<quiet.length;i++){
            pos[quiet[i]] = i;
        }
        ret = new int[quiet.length];
        cache = new int[quiet.length];
        Arrays.fill(cache,-1);
        for (int i=0;i<quiet.length;i++){
            ret[i] = pos[dfs(map,quiet,i)];
        }
        return ret;
    }

    private int dfs(List<Integer>[] map, int[] quiet,int key) {
        if(map[key] == null) return quiet[key];
        if(cache[key] != -1) return cache[key];
        int min = quiet[key];
        for (int index:map[key]){
             min = Math.min(min,dfs(map,quiet,index));
        }
        return cache[key] = min;
    }

    @Test
    public void ee(){
        containsNearbyDuplicate(new int[]{1,2,3,1},3);
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);
        }
        for (List<Integer> cur:map.values()){
            for (int i=0;i<cur.size()-1;i++){
                if(cur.get(i+1)-cur.get(i)<k){
                    return true;
                }
            }
        }
        return false;
    }
}
